package cn.demoncat.util.lang.entity.data;

import cn.demoncat.util.lang.entity.report.Count;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;

/**
 * 二叉树
 * 
 * 存储：链表（二叉链表） 功能：通过链表来实现二叉树的数据结构
 * 
 * @author 延晓磊
 *
 * @since 2020年7月18日
 */
public class BinaryTree<T> {

	// 根结点
	protected BinaryTreeNode<T> root;

	// 线索化 - 上个结点的指针，非空表示已线索化
	protected BinaryTreeNode<T> pre;

	/**
	 * 构建
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public BinaryTree() {
		super();
	}

	/**
	 * 构建
	 * 
	 * @param root
	 *            根结点
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public BinaryTree(BinaryTreeNode<T> root) {
		super();
		this.root = root;
	}

	/**
	 * 树根
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月21日
	 */
	public BinaryTreeNode<T> getRoot() {
		return root;
	}

	public void setRoot(BinaryTreeNode<T> root) {
		this.root = root;
	}

	/**
	 * 前序遍历：结点 > 左子树 > 右子树
	 * 
	 * @param fn
	 *            消费(数据)
	 * 
	 * @return 是否遍历（链表为空返回false）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean preOrder(Consumer<T> fn) {
		if (root == null) {
			return false;
		}
		// 从根结点开始遍历
		root.preOrder(fn);
		return true;
	}

	/**
	 * 中序遍历：左子树 > 结点 > 右子树
	 * 
	 * @param fn
	 *            消费(数据)
	 * 
	 * @return 是否遍历（链表为空返回false）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean inOrder(Consumer<T> fn) {
		if (root == null) {
			return false;
		}
		// 从根结点开始遍历
		root.inOrder(fn);
		return true;
	}

	/**
	 * 后序遍历：左子树 > 右子树 > 结点
	 * 
	 * @param fn
	 *            消费(数据)
	 * 
	 * @return 是否遍历（链表为空返回false）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean postOrder(Consumer<T> fn) {
		if (root == null) {
			return false;
		}
		// 从根结点开始遍历
		root.postOrder(fn);
		return true;
	}

	/**
	 * 前序遍历：结点 > 左子树 > 右子树
	 * 
	 * @param fn
	 *            消费(结点)
	 * 
	 * @return 是否遍历（链表为空返回false）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean preOrderNode(Consumer<BinaryTreeNode<T>> fn) {
		if (root == null) {
			return false;
		}
		// 从根结点开始遍历
		root.preOrderNode(fn);
		return true;
	}

	/**
	 * 中序遍历：左子树 > 结点 > 右子树
	 * 
	 * @param fn
	 *            消费(结点)
	 * 
	 * @return 是否遍历（链表为空返回false）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean inOrderNode(Consumer<BinaryTreeNode<T>> fn) {
		if (root == null) {
			return false;
		}
		// 从根结点开始遍历
		root.inOrderNode(fn);
		return true;
	}

	/**
	 * 后序遍历：左子树 > 右子树 > 结点
	 * 
	 * @param fn
	 *            消费(结点)
	 * 
	 * @return 是否遍历（链表为空返回false）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean postOrderNode(Consumer<BinaryTreeNode<T>> fn) {
		if (root == null) {
			return false;
		}
		// 从根结点开始遍历
		root.postOrderNode(fn);
		return true;
	}

	/**
	 * 是否为空树
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月23日
	 */
	public boolean isEmpty() {
		return root == null;
	}

	/**
	 * 长度
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月22日
	 */
	public int size() {
		Count count = new Count();
		// 遍历统计
		preOrder(o -> count.addCount());
		return (int) count.getCount();
	}

	/**
	 * 转换为列表 - 中序遍历（对二叉排序树有序）
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月23日
	 */
	public List<T> toList() {
		List<T> list = new ArrayList<>();
		// 遍历添加
		inOrder(list::add);
		return list;
	}

	/**
	 * 查找结点
	 * 
	 * @param data
	 *            数据
	 * 
	 * @return 第一个查找到的结点，未找到返回null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public BinaryTreeNode<T> search(T data) {
		if (root == null) {
			return null;
		}
		return root.search(data);
	}

	/**
	 * 删除结点：叶子结点-删除结点，分枝结点-删除子树
	 * 
	 * @param data
	 *            目标数据（删除第一个匹配到的结点）
	 * 
	 * @return 是否删除
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean removes(T data) {
		/*
		 * ======================== 说明 =======================
		 * 1、删除结点，实际是清除父结点的关联指针（左结点置空父结点的left，右结点置空父结点的right）
		 * 2、对于单向二叉树，需要从根结点遍历（逐个比较左右结点），才能找到父结点 3、如果是叶子结点，可以直接删除；如果是分枝结点，删除后整个子树都会退出链表
		 * ====================================================
		 */
		if (root != null) {
			// 判断根结点
			if (data.equals(root.data)) {
				// 删除根结点
				root = null;
				return true;
			} else {
				// 遍历树，找到第一个匹配数据的结点并删除
				return root.removes(data);
			}
		}
		return false;
	}

	/**
	 * 中序线索化
	 * 
	 * 1、只能线索化一次 2、线索化后，指针会被扰乱，所以只能通过threadOrder遍历 3、线索化后，指针会被扰乱，所以不能再添加和删除结点
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public void toThreaded() {
		if (pre == null) {
			toThreaded(root);
		}
	}

	/**
	 * 中序线索化遍历
	 * 
	 * @param fn
	 *            消费(数据)
	 * 
	 * @return 是否遍历（链表为空返回false）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean threadedOrder(Consumer<T> fn) {
		if (root == null) {
			return false;
		}
		// 从根结点开始遍历
		BinaryTreeNode<T> node = root;
		while (node != null) {
			// 找到第一个有前驱的结点（线索化处理的结点）
			while (node.leftType == 0) {
				node = node.left;
			}
			// 处理当前结点
			fn.accept(node.data);
			// 处理后继结点
			while (node.rightType == 1) {
				node = node.right;
				fn.accept(node.data);
			}
			// 切换结点
			node = node.right;
		}
		return true;
	}

	/**
	 * 查找祖先结点（父结点 > 爷结点 ... 根结点）
	 * 
	 * @param node
	 *            目标结点
	 * @param fn
	 *            消费（结点）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月22日
	 */
	public void findParents(BinaryTreeNode<T> node, Consumer<BinaryTreeNode<T>> fn) {
		if (root != null && root != node) {
			findParents(root, node, fn);
		}
	}

	/**
	 * 打印 - 中序遍历（遍历二叉排序树时有序）
	 * 
	 * @return
	 *
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	@Override
	public String toString() {
		StringBuilder sd = new StringBuilder("[");
		if (pre == null) {
			// 中序遍历
			if (inOrder(data -> sd.append(data).append(", "))) {
				sd.delete(sd.length() - 2, sd.length());
			}
		} else {
			// 中序线索化遍历
			if (threadedOrder(data -> sd.append(data).append(", "))) {
				sd.delete(sd.length() - 2, sd.length());
			}
		}
		sd.append("]");
		return sd.toString();
	}

	/**
	 * 中序线索化
	 * 
	 * @param node
	 *            当前结点
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	private void toThreaded(BinaryTreeNode<T> node) {
		if (node == null) {
			return;
		}
		// 线索化左子树
		toThreaded(node.left);
		// 线索化当前结点
		if (node.left == null) {
			// 当前结点的左指针为空，指定上一个结点为前驱
			node.left = pre;
			node.leftType = 1;
		}
		if (pre != null && pre.right == null) {
			// 上一个结点的右指针为空，指定当前结点为后继
			pre.right = node;
			pre.rightType = 1;
		}
		pre = node;
		// 线索化右子树
		toThreaded(node.right);
	}

	/**
	 * 查找祖先结点
	 * 
	 * @param parent
	 *            父结点
	 * @param node
	 *            目标结点
	 * @param fn
	 *            消费（结点）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月22日
	 */
	private boolean findParents(BinaryTreeNode<T> parent, BinaryTreeNode<T> node, Consumer<BinaryTreeNode<T>> fn) {
		if (parent.left == node || parent.right == node) {
			// 父结点
			fn.accept(parent);
			return true;
		} else {
			if (parent.left != null) {
				if (findParents(parent.left, node, fn)) {
					// 祖先结点
					fn.accept(parent);
					return true;
				}
			} else if (parent.right != null) {
				if (findParents(parent.right, node, fn)) {
					// 祖先结点
					fn.accept(parent);
					return true;
				}
			}
			return false;
		}
	}

	
}
